package vg.services.graph_view_manager.realization.graph_comparison.algorithm;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import vg.services.data_base_manager.data.graph.Attribute;
import vg.services.data_base_manager.data.graph.AttributeItem;
import vg.services.data_base_manager.data.graph.Edge;
import vg.services.data_base_manager.data.graph.Graph;
import vg.services.data_base_manager.data.graph.Vertex;

public class GraphComparisonAlghoritm {
	// Defines
	private static final float DEF_EPSILON = 0.00001f;
	private static final String DEF_INPUT_EDGE = "system_input_edge";
	private static final String DEF_OUTPUT_EDGE = "system_output_edge";
	
	private static final double DEF_MAX_PERCENT_VALUE = 1.0d;
	private static final double DEF_MIN_PERCENT_VALUE = 0.0d;
	
	// Main data
	private Graph g1, g2;
	private int g1VertexCount = 0, g1EdgeCount = 0;
	private int g2VertexCount = 0, g2EdgeCount = 0;
	
	// vertex -> index
	private Map<Vertex, Integer> g1Vertex2Idx;
	private Map<Vertex, Integer> g2Vertex2Idx;
	// index -> vertex
	private Map<Integer, Vertex> g1Idx2Vertex; 
	private Map<Integer, Vertex> g2Idx2Vertex;
	// edge -> index
	private Map<Edge, Integer> g1Edge2Idx;
	private Map<Edge, Integer> g2Edge2Idx;
	// index -> edge
	private Map<Integer, Edge> g1Idx2Edge; 
	private Map<Integer, Edge> g2Idx2Edge;
	
	// FIX ME
	private int[] in1; // vertex idx -> input edges
	private int[] out1; // vertex idx -> output edges	
	private int[] in2; // vertex idx -> input edges
	private int[] out2; // vertex idx -> output edges
	
	private Map<String, Double> vertex_attribute_table;
	private Map<String, Double> edge_attribute_table;
	
	private float[][] vertex_matching_table;
	private float[][] edge_matching_table;
	
	private float edge_barrier = 0.5f;
	private float vertex_barrier = 0.5f;

//=============================================================================	
//-----------------Constructors	
	public GraphComparisonAlghoritm(Graph g1, Graph g2) {
		this.g1 = g1;
		this.g2 = g2;
		init();
	}
	
//=============================================================================	
//-----------------Public methods	
	public Graph run() {
		// Phase 1
		build_attribute_tables();
		
		// Phase 2
		build_matching_tables();
		
		// Phase 3
		Solution best_solution = matching();
		
		// Phase 4
		Graph graph = build_mcs(best_solution);
		
		return graph;
	}
//=============================================================================
//-----------------PRIVATE METHODS---------------------------------------------
//-----------------Build maximal common graph	
	private Graph build_mcs(Solution solution) {
		if (solution == null || solution.getVertices() == null || solution.getVertices().length == 0) return new Graph(g1.isDirected() | g2.isDirected());
		
		MCSVertex[] vertices = solution.getVertices();
		// build vertices
		Vertex[][] new_vertex_table = new Vertex[g1VertexCount][g2VertexCount];
		List<Vertex> new_vertices = new ArrayList<Vertex>(); 
		for (int i = 0; i < vertices.length; i++) {
			int idx1 = vertices[i].getSrc();
			int idx2 = vertices[i].getDst();
			Vertex v1 = g1Idx2Vertex.get(idx1);
			Vertex v2 = g2Idx2Vertex.get(idx2);
			Vertex v = new Vertex(mergingAttributeItems(v1, v2));
			new_vertex_table[idx1][idx2] = v;
			new_vertices.add(v);
		}
		
		// build edges
		List<Edge> new_edges = new ArrayList<Edge>();
		for (int i = 0; i < vertices.length; i++) {
			for (int j = i + 1; j < vertices.length; j++) {
				MCSVertex mcs_v1 = vertices[i];
				MCSVertex mcs_v2 = vertices[j];
				int g1Idx1 = mcs_v1.getSrc();
				int g1Idx2 = mcs_v2.getSrc();
				int g2Idx1 = mcs_v1.getDst();
				int g2Idx2 = mcs_v2.getDst();
				Map<Edge, Float> tmp_edges1 = mergingEdges(mcs_v1, mcs_v2, new_vertex_table[g1Idx1][g2Idx1], new_vertex_table[g1Idx2][g2Idx2]);
				new_edges.addAll(tmp_edges1.keySet());
				Map<Edge, Float> tmp_edges2 = mergingEdges(mcs_v2, mcs_v1, new_vertex_table[g1Idx2][g2Idx2], new_vertex_table[g1Idx1][g2Idx1]);
				new_edges.addAll(tmp_edges2.keySet());
			}
		}
		
		// build graph
		return new Graph(new_vertices, new_edges, g1.isDirected() | g2.isDirected());
	}
	
	private float quick_build_mcs(Solution solution) {		
		if (solution == null || solution.getVertices() == null || solution.getVertices().length == 0) return 0;

		MCSVertex[] vertices = solution.getVertices();		
		// build vertices
		float vertex_result = 0;
		Vertex[][] new_vertex_table = new Vertex[g1VertexCount][g2VertexCount];
		List<Vertex> new_vertices = new ArrayList<Vertex>(); 
		for (int i = 0; i < vertices.length; i++) {
			int idx1 = vertices[i].getSrc();
			int idx2 = vertices[i].getDst();
			Vertex v1 = g1Idx2Vertex.get(idx1);
			Vertex v2 = g2Idx2Vertex.get(idx2);
			Vertex v = new Vertex(mergingAttributeItems(v1, v2));
			vertex_result += vertex_matching_table[idx1][idx2];
			new_vertex_table[idx1][idx2] = v;
			new_vertices.add(v);
		}
		
		// build edges
		float edge_result = 0;
		List<Edge> new_edges = new ArrayList<Edge>();
		for (int i = 0; i < vertices.length; i++) {
			for (int j = i + 1; j < vertices.length; j++) {
				MCSVertex mcs_v1 = vertices[i];
				MCSVertex mcs_v2 = vertices[j];
				int g1Idx1 = mcs_v1.getSrc();
				int g1Idx2 = mcs_v2.getSrc();
				int g2Idx1 = mcs_v1.getDst();
				int g2Idx2 = mcs_v2.getDst();
				
				Map<Edge, Float> tmp_edges1 = mergingEdges(mcs_v1, mcs_v2, new_vertex_table[g1Idx1][g2Idx1], new_vertex_table[g1Idx2][g2Idx2]);
				new_edges.addAll(tmp_edges1.keySet());
				for (Float ratio : tmp_edges1.values())
					edge_result += ratio;
				
				Map<Edge, Float> tmp_edges2 = mergingEdges(mcs_v2, mcs_v1, new_vertex_table[g1Idx2][g2Idx2], new_vertex_table[g1Idx1][g2Idx1]);
				new_edges.addAll(tmp_edges2.keySet());
				for (Float ratio : tmp_edges2.values())
					edge_result += ratio;
			}
		}
		
		// build graph
		return (vertex_result + edge_result);
	}

//=============================================================================
//-----------------Matching
	private Solution matching() {
		// Debug info
		for (int i = 0; i < g1VertexCount; i++) {
			for (int j = 0; j < g2VertexCount; j++) {
				System.out.printf("%.2f ", vertex_matching_table[i][j]);
			}
			System.out.println();
		}
		
		//---------------------------------------
		Solution best_solution = null;
		float best_ratio = 0;
		float barrier = 0.1f;
		BigDecimal barrierCases = new BigDecimal(200000);
		
		while (barrier < 1) {
			SolutionSet solutionSet = new SolutionSet(vertex_matching_table, barrier);
			System.out.println(solutionSet.roughSize().toString());
			if (solutionSet.roughSize().compareTo(barrierCases) <= 0) {
				while (solutionSet.hasNext()) {
					Solution solution = solutionSet.curr();
					System.out.println(solution.toString());
					
					float ratio = quick_build_mcs(solution);
					if (ratio > best_ratio) {
						best_ratio = ratio;
						best_solution = solution;
						System.out.println("New best ratio = " + ratio);
					}
					
					solutionSet.next();
				}
				break;
			}
			barrier += 0.002f;
		}
		return best_solution;
	}
	
	private void build_matching_tables() {
		build_vertex_matching_table();
		build_edge_matching_table();
		normolize(vertex_matching_table);
		normolize(edge_matching_table);
	}
	
	private void build_vertex_matching_table() {
		if (g1VertexCount <= 0 || g2VertexCount <= 0) {
			vertex_matching_table = null;
		} else {
			vertex_matching_table = new float[g1VertexCount][g2VertexCount];
		}
				
		for (Vertex v1 : g1.getVertices()) {
			for(Vertex v2 : g2.getVertices()) {
				int idx1 = g1Vertex2Idx.get(v1);
				int idx2 = g2Vertex2Idx.get(v2);
				vertex_matching_table[idx1][idx2] = vertex_matching4couple(v1, v2);
			}
		}		
	}
	
	private void build_edge_matching_table() {
		if (g1EdgeCount <= 0 || g2EdgeCount <= 0) {
			edge_matching_table = null;
		} else {
			edge_matching_table = new float[g1EdgeCount][g2EdgeCount];
		}
				
		for (Edge e1 : g1.getEdges()) {
			for(Edge e2 : g2.getEdges()) {
				int idx1 = g1Edge2Idx.get(e1);
				int idx2 = g2Edge2Idx.get(e2);
				edge_matching_table[idx1][idx2] = edge_matching4couple(e1, e2);
			}
		}
	}
	
	private void normolize(float[][] array) {
		float max = 0;
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				if (max < array[i][j])
					max = array[i][j];
			}
		}

		if (max == 0) max = 1.0f;
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				array[i][j] /= max;
			}
		}
	}

//=============================================================================
//-----------------Build tables for attributes	
	private void build_attribute_tables() {
		build_vertex_attribute_table();
		build_edge_attribute_table();
	}
	
	private void build_vertex_attribute_table() {
		vertex_attribute_table = new HashMap<String, Double>();
		vertex_attribute_table.put(DEF_INPUT_EDGE, DEF_MAX_PERCENT_VALUE * 1); // 100%
		vertex_attribute_table.put(DEF_OUTPUT_EDGE, DEF_MAX_PERCENT_VALUE * 1); // 100%
		add_attributes2vertex_attribute_table(g1);
		add_attributes2vertex_attribute_table(g2);
	}
	
	private void build_edge_attribute_table() {
		edge_attribute_table = new HashMap<String, Double>();
		add_attributes2edge_attribute_table(g1);
		add_attributes2edge_attribute_table(g2);
	}
	
	// Note: edge_attribute_table != null
	private void add_attributes2vertex_attribute_table(Graph g) {
		if (g != null) {
			Collection<Vertex> vertices = g.getVertices();
			if (vertices != null && vertices.size() > 0) {
				for (Vertex v : vertices) {
					List<Attribute> attributes = v.getAttributes();
					if (attributes != null) {
						for (Attribute a : attributes) {
							String name = a.getName();
							if (name != null) {
								vertex_attribute_table.put(name, DEF_MIN_PERCENT_VALUE);
							}
						}
					}
				}
			}
		}		
	}
	
	// Note: edge_attribute_table != null
	private void add_attributes2edge_attribute_table(Graph g) {
		if (g != null) {
			Collection<Edge> edges = g.getEdges();
			if (edges != null && edges.size() > 0) {
				for (Edge e : edges) {
					List<Attribute> attributes = e.getAttributes();
					if (attributes != null) {
						for (Attribute a : attributes) {
							String name = a.getName();
							if (name != null) {
								edge_attribute_table.put(name, DEF_MIN_PERCENT_VALUE);
							}
						}
					}
				}
			}
		}
	}
//=============================================================================
//-----------------Initialize method		
	// Method for initializing main data
	private void init() {
		// initialize  vertex -> table index tables
		if (g1 != null) {
			Collection<Vertex> vertices = g1.getVertices();
			if (vertices != null && vertices.size() > 0) {
				g1VertexCount = vertices.size();
				g1Vertex2Idx = new HashMap<Vertex, Integer>(vertices.size());
				g1Idx2Vertex = new HashMap<Integer, Vertex>(vertices.size());
				in1 = new int[vertices.size()];
				out1 = new int[vertices.size()];
				int i = 0;
				for(Vertex v: vertices) {
					g1Vertex2Idx.put(v, i);
					g1Idx2Vertex.put(i, v);
					i++;
				}
			}
		}
		
		if (g2 != null) {
			Collection<Vertex> vertices = g2.getVertices();
			if (vertices != null && vertices.size() > 0) {
				g2VertexCount = vertices.size();
				g2Vertex2Idx = new HashMap<Vertex, Integer>(vertices.size());
				g2Idx2Vertex = new HashMap<Integer, Vertex>(vertices.size());
				in2 = new int[vertices.size()];
				out2 = new int[vertices.size()];
				int i = 0;
				for(Vertex v: vertices) {
					g2Vertex2Idx.put(v, i);
					g2Idx2Vertex.put(i, v);
					i++;
				}
			}
		}
		
		// calculate input and output edges for each vertex
		if (g1 != null) {
			Collection<Edge> edges = g1.getEdges();
			if (edges != null && edges.size() > 0) {
				g1EdgeCount = edges.size();
				g1Edge2Idx = new HashMap<Edge, Integer>(edges.size());
				g1Idx2Edge = new HashMap<Integer, Edge>(edges.size());
				int i = 0;
				for (Edge e : edges) {
					g1Edge2Idx.put(e, i);
					g1Idx2Edge.put(i, e);
					if (g1.isDirected()) {
						in1[g1Vertex2Idx.get(e.getSource())]++;
						out1[g1Vertex2Idx.get(e.getTarget())]++;
					} else {
						in1[g1Vertex2Idx.get(e.getSource())] += 2;
						out1[g1Vertex2Idx.get(e.getTarget())] += 2;						
					}
					i++;
				}
			}
		}
		
		if (g2 != null) {
			Collection<Edge> edges = g2.getEdges();
			if (edges != null && edges.size() > 0) {
				g2EdgeCount = edges.size();
				g2Edge2Idx = new HashMap<Edge, Integer>(edges.size());
				g2Idx2Edge = new HashMap<Integer, Edge>(edges.size());
				int i = 0;
				for (Edge e : edges) {
					g2Edge2Idx.put(e, i);
					g2Idx2Edge.put(i, e);
					if (g2.isDirected()) {
						in2[g2Vertex2Idx.get(e.getSource())]++;
						out2[g2Vertex2Idx.get(e.getTarget())]++;
					} else {
						in2[g2Vertex2Idx.get(e.getSource())] += 2;
						out2[g2Vertex2Idx.get(e.getTarget())] += 2;						
					}
					i++;
				}
			}
		}
	}

//=============================================================================
//-----------------Matching methods		
	private float vertex_matching4couple(Vertex v1, Vertex v2) {
		float result = 0;
		for (String attr : vertex_attribute_table.keySet()) {
			double match = 0;
			if (attr.equals(DEF_INPUT_EDGE)) {
				match = real_diff(in1[g1Vertex2Idx.get(v1)], in2[g2Vertex2Idx.get(v2)]);
			} else if (attr.equals(DEF_OUTPUT_EDGE)){
				match = real_diff(out1[g1Vertex2Idx.get(v1)], out2[g2Vertex2Idx.get(v2)]);
			} else {
				Attribute a1 = find_attr(attr, v1);
				Attribute a2 = find_attr(attr, v2);
				if (a1 != null && a2 != null) {
					if (a1.isRealType() && a2.isRealType()) {
						// Integer class
						match = real_diff(Double.parseDouble(a1.getValue()), Double.parseDouble(a2.getValue()));
					} else {
						// String class for other
						match = string_diff(a1.getValue(), a2.getValue());
					}
				}
			}
			result += (match * vertex_attribute_table.get(attr));
		}
		
		// not zero
		result += DEF_EPSILON;
		
		return result;
	}
	
	private float edge_matching4couple(Edge e1, Edge e2) {
		float result = 0;
		for (String attr : edge_attribute_table.keySet()) {
			double match = 0;
			Attribute a1 = find_attr(attr, e1);
			Attribute a2 = find_attr(attr, e2);
			if (a1 != null && a2 != null) {
				if (a1.isRealType() && a2.isRealType()) {
					// Integer class
					match = real_diff(Double.parseDouble(a1.getValue()), Double.parseDouble(a2.getValue()));
				} else {
					// String class for other
					match = string_diff(a1.getValue(), a2.getValue());
				}
			}
			
			result += (match * edge_attribute_table.get(attr));
		}
		
		// not zero
		result += DEF_EPSILON;
		
		return result;
	}
	
	// Note: range from 0 to 1
	private double real_diff(double value1, double value2) {
		double diff = 0;
		
		if (value1 < 0 && value2 < 0) {
			value1 = -value1;
			value2 = -value2;
		}
		
		if (value1 < 0 && value2 > 0) {
			value1 = -value1;
			value2 = value1 + value2; 
		}
		
		if (value2 < 0 && value1 > 0) {
			value2 = - value2;
			value1 = value1 + value2;
		}
		
		// not zero
		value1++;
		value2++;
		
		
		if (value1 > value2)
			diff = value2 / value1;
		else
			diff = value1 / value2;
		
		if (diff > 1) diff = 1;
		if (diff < 0) diff = 0;
		
		return  diff;
	}

	// Note: range from 0 to 1
	private double string_diff(String value1, String value2) {
		double diff = 0;
		
		if (value1 == null || value2 == null)
			return diff;
		
		byte[] bytes2 = value2.getBytes();
		int i = 0;
		for (byte b : value1.getBytes()) {
			if (bytes2.length <= i || b != bytes2[i]) {
				break;
			} else {
				i++;
			}
		}
		diff = (2 * i) / (double)(value1.length() + value2.length());

		if (diff > 1) diff = 1;
		if (diff < 0) diff = 0;
		
		return  diff;
	}
	
	private Attribute find_attr(String attribute, AttributeItem item) {
		if (item != null && attribute != null) {
			List<Attribute> attributes = item.getAttributes();
			for (Attribute attr : attributes) {
				if (attribute.equals(attr.getName()))
					return attr;
			}
		}
		
		return null;
	}
	
	private AttributeItem mergingAttributeItems(AttributeItem item1, AttributeItem item2) {
		List<Attribute> attributes = new ArrayList<Attribute>();
		for (Attribute attr1 : item1.getAttributes()) {
			Attribute attr2 = find_attr(attr1.getName(), item2);
			if (attr2 != null) {
				attributes.add(new Attribute(attr1.getName(), attr1.getValue() + "/" + attr2.getValue(), String.class));
			} else {
				attributes.add(new Attribute(attr1.getName(), attr1.getValue() + "/null", String.class));
			}
		}
		return new AttributeItem(attributes);
	}
	
	/**
	 * Returns shared edges between v1 and v2.
	 * @param v1 - src vertex
	 * @param v2 - dst vertex
	 */
	private Map<Edge, Float> mergingEdges(MCSVertex v1, MCSVertex v2, Vertex new_v1, Vertex new_v2) {
		Map<Edge, Float> edges = new HashMap<Edge, Float>();
		
		int g1Idx1 = v1.getSrc();
		int g1Idx2 = v2.getSrc();
		int g2Idx1 = v1.getDst();
		int g2Idx2 = v2.getDst();
		
		Vertex g1v1 = g1Idx2Vertex.get(g1Idx1);
		Vertex g1v2 = g1Idx2Vertex.get(g1Idx2);
		Vertex g2v1 = g2Idx2Vertex.get(g2Idx1);
		Vertex g2v2 = g2Idx2Vertex.get(g2Idx2);
		
		List<Edge> g1Edges = new ArrayList<Edge>();
		for (Edge e : g1.getEdges()) {
			Vertex src = e.getSource(), trg = e.getTarget();
			
			if (src == null || trg == null) continue;
			
			if (src.equals(g1v1) && trg.equals(g1v2)) {
				g1Edges.add(e);
			}
		}

		List<Edge> g2Edges = new ArrayList<Edge>();
		for (Edge e : g2.getEdges()) {
			Vertex src = e.getSource(), trg = e.getTarget();
			
			if (src == null || trg == null) continue;
			
			if (src.equals(g2v1) && trg.equals(g2v2)) {
				g2Edges.add(e);
			}
		}
		
		// merging
		if (g1Edges.size() > 0 && g2Edges.size() > 0) {
			float[][] table = new float[g1Edges.size()][g2Edges.size()];
			int i = 0, j = 0;
			for (Edge e1 : g1Edges) {
				for (Edge e2 : g2Edges) {
					int idx1 = g1Edge2Idx.get(e1);
					int idx2 = g2Edge2Idx.get(e2);
					table[i][j] = edge_matching_table[idx1][idx2];
					j++;
				}
				i++;
			}
			
			int[][] assignment = HungarianAlgorithm.hgAlgorithm(table, "max");
			
			for (i = 0; i < assignment.length; i++) {
				Edge e1 = g1Edges.get(assignment[i][0]);
				Edge e2 = g2Edges.get(assignment[i][1]);
				int idx1 = g1Edge2Idx.get(e1);
				int idx2 = g2Edge2Idx.get(e2);
				float ratio = edge_matching_table[idx1][idx2];
				if (ratio >= edge_barrier) {
					edges.put(new Edge(new_v1, new_v2, mergingAttributeItems(e1, e2)), ratio);
				}
			}
		}
		
		return edges;
	}
}
